class Solution {
    String s;
    int k;
    public int longestSubstring(String _s, int _k) {
        s = _s;
        k = _k;
        return dfs(0,s.length()-1);
    }
    public int dfs(int l,int r) {
        //统计l到r之间的字符个数
        int[] count = new int[26];
        for(int i=l;i<=r;i++) {
            count[s.charAt(i)-'a']++;
        }
        //分割字符(如果找到一个没到k个的 就开始分治 反之直接返回)
        char ch = 0;
        //遍历count数组找分割字符
        for(int i=0;i<26;i++) {
            if(count[i]>0 && count[i]<k) {
                //找到了:l到r这个子串一定不符合
                ch = (char) ('a'+ i);
                break;
            }
        }
        //没找到：满足条件，返回长度
        if(ch==0) return r-l+1;
        int ret = 0;
        //以ch为分割字符:重新找l和r
        for(int i=l;i<=r;) {
            while(i<=r && s.charAt(i)==ch) i++;
            //l都找不到直接返回0即可
            if(i>r) break;
            int start = i;
            while(i<=r && s.charAt(i)!=ch) i++;
            int cur = dfs(start,i-1);
            ret = Math.max(ret,cur);
        }
        return ret;
    }
}